<?php
/**
 * User: helloJiu
 * Date: 2021/10/25
 * Time: 17:17
 */

namespace App\Algorithm\DP;


class Bag
{
    public function handle($n, $w, $wt, $val)
    {
        // dp[i][w]表示：对于前i个物品，背包的容量为w时，这种情况下可以装下的最大价值是dp[i][w]。
        $dp = [];

        for ($i = 0; $i <= $n; $i++) {
            // 总量为0时, 不能装
            $dp[$i][0] = 0;
        }
        for ($j = 1; $j <= $w; $j++) {
            // 物品为0是, 不能装
            $dp[0][$j] = 0;
        }

        for ($i = 1; $i <= $n; $i++) {
            // 从前$i件物品中随意选, 对于不同重量背包所得到的最大价值
            for ($j = 1; $j <= $w; $j++) {
                // 如果选择的话, 剩余重量
                $remain_w = $j - $wt[$i - 1];
                if ($remain_w < 0) {
                    // 装不下
                    $dp[$i][$j] = $dp[$i - 1][$j];
                } else {
                    // 装或者不装得到的最大价值 取更大的
                    // $dp[$i-1][$remain_w] 从$i-1件物品中随意选对于重量是$remain_w得到的最大价值
                    $dp[$i][$j] = max(
                        $dp[$i - 1][$remain_w] + $val[$i - 1],  // 选择了
                        $dp[$i - 1][$j]  // 没有选择
                    );
                }
            }
        }
        // print_r($dp);
        return $dp[$n][$w];
    }

    public function handle1($n, $w, $wt, $val)
    {
        // dp[j]表示：表示背包容量为j时包含的最大价值
        $dp = [];

        for ($j = 0; $j <= $w; $j++) {
            $dp[$j] = 0;
        }

        for ($i = 1; $i <= $n; $i++) {
            // 两层循环, 表示遍历到某件物品时, 需要重新计算$dp中的各重量对应的最大价值
            for ($j = $w; $j > 0; $j--) {
                // 需要逆序遍历, 比较大小时, $dp[$remain_w] 中还没有包含$i件物品
                // 如果正序遍历, 比较大小时, $dp[$remain_w] 中可能已经包含$i件物品的价值, 相当于$i物品多算了, 产生错误结果
                $remain_w = $j - $wt[$i - 1];
                if ($remain_w >= 0) {
                    $dp[$j] = max(($dp[$remain_w] + $val[$i-1]), $dp[$j]);
                }
            }
        }
        return $dp[$w];
    }
}